package s4_栈;

import java.util.*;

/**
 * @author wisdomelon
 * @date 2020/7/27 0027
 * @project data_study
 * @jdk 1.8
 * 逆波兰表达式
 */
public class PolandNotation {

    public static final List<String> operate = Arrays.asList(new String[]{"+","-","*","/"});

    public static void main(String[] args) {

        //String expression = "1+((2+3)*4)-5";
        String expression = "1+2*3-4";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println(infixExpressionList);

        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        System.out.println(suffixExpressionList);

        Stack<Integer> stack = new Stack<>();

        Iterator<String> iterator = suffixExpressionList.iterator();
        while(iterator.hasNext()) {
            String val = iterator.next();

            if(operate.contains(val)) {
                int second = stack.pop();
                int first = stack.pop();
                int res = methods(first, second, val);
                stack.push(res);
            } else {
                stack.push(Integer.parseInt(val));
            }
        }

        int result = stack.pop();
        System.out.println(result);


    }

    /**
     * 将中缀表达式 list 转换为后缀表达式 list
     * @param infixExpressionList
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> infixExpressionList) {

        // 操作方法栈
        Stack<String> operate = new Stack<>();

        List<String> suffixExpressionList = new ArrayList<>();

        for(String item: infixExpressionList) {

            if(item.matches("\\d+")) {
                // 如果是数，则加入到 suffixExpressionList 中
                suffixExpressionList.add(item);
            } else if("(".equals(item)) {
                operate.push(item);
            } else if (")".equals(item)) {
                while(!"(".equals(operate.peek())) {
                    suffixExpressionList.add(operate.pop());
                }
                // 将 ( 弹出
                operate.pop();
            } else {
                // 当 item 的优先级小于等于 operate 栈顶的运算符，则将operate栈顶的运算符弹出并加入到s2中， 循环比较
                while(operate.size() != 0 && Operation.getValue(operate.peek()) >= Operation.getValue(item)) {
                    suffixExpressionList.add(operate.pop());
                }
                // 还需要将 item 压入栈中
                operate.push(item);
            }
        }

        // 将 operate 剩余的元素加入到 suffixExpressionList
        while(operate.size() != 0) {
            suffixExpressionList.add(operate.pop());
        }

        return suffixExpressionList;
    }

    /**
     * 将中缀表达式转换成对应的list
     * @param exp 1+((2+3)*4)-5
     * @return  1, +, (, (, 2, +, 3, ), *, 4, ), -, 5
     */
    public static List<String> toInfixExpressionList(String exp) {

        List<String> ls = new ArrayList<>();

        // 用于遍历 exp
        int i = 0;
        // 用于存放多位数
        String str;
        // 遍历到的每一个字符
        char c;
        do{
            // 如果c是一个非数字，需要加入到ls
            if((c = exp.charAt(i)) < 48 || (c = exp.charAt(i)) > 57) {
                ls.add(c + "");
                i++;
            } else {
                // 如果是一个数字，则要进行拼接，需要考虑多位数
                str = "";
                while(i < exp.length() && (c = exp.charAt(i)) >= 48 && (c = exp.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);

            }
        } while (i < exp.length());

        return ls;
    }


    /**
     * 计算结果
     * @param first
     * @param second
     * @param operate
     * @return
     */
    private static int methods(int first, int second, String operate) {

        int res = 0;

        switch (operate) {
            case "+":
                res = first + second;
                break;
            case "-":
                res = first - second;
                break;
            case "*":
                res = first * second;
                break;
            case "/":
                res = first / second;
                break;
            default:
                break;
        }

        return res;

    }
}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    /**
     * 返回操作符对应的优先级
     * @param operation
     * @return
     */
    public static int getValue(String operation) {
        int res = 0;
        switch (operation) {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                break;
        }
        return res;
    }
}
